import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-146-LRU缓存
 * @date 2025/4/29 15:12
 */
public class LRUCache {

    // 内部类构造双端链表
    public class DLinkNode {
        int key;
        int val;
        DLinkNode prev;
        DLinkNode next;

        public DLinkNode() {
        }

        public DLinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private int capacity;
    private Map<Integer, DLinkNode> map; // 实现O(1)的get时间复杂度
    private DLinkNode head;
    private DLinkNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new DLinkNode();
        tail = new DLinkNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            DLinkNode node = map.get(key);
            moveToHead(node);
            return node.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)) {
            if (map.size() >= capacity) {
                // 一定要先删除map，不然后续的tail.prev会变化
                map.remove(tail.prev.key);
                removeNode(tail.prev);
            }
            DLinkNode node = new DLinkNode(key, value);
            map.put(key, node);
            addToHead(node);
        } else {
            DLinkNode node = map.get(key);
            node.val = value;
            moveToHead(node);
        }
    }

    private void moveToHead(DLinkNode node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(DLinkNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkNode node) {
        // 并不是真正的删除这个节点
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
